package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1621. 大小为 K 的不重叠线段的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/19 16:58
 */
public class NumberOfSets {

    public static void main(String[] args) {
        NumberOfSets test = new NumberOfSets();

        // 796297179
//        int n = 30;
//        int k = 7;

        // 93918749
//        int n = 1000;
//        int k = 350;

        // 3
        int n = 3;
        int k = 1;

        int i = test.numberOfSets(n, k);
        System.out.println(i);
    }

    public int numberOfSets(int n, int k) {
        n--;
        long[][] arr = new long[k][n];
        long[] ints = arr[0];
        ints[0] = 1;
        for (int i = 1; i < n; i++) {
            ints[i] = (ints[i - 1] + i + 1) % 1000000007;
        }
        for (int i = 1; i < k; i++) {
            ints = arr[i];
            long[] last = arr[i - 1];
            ints[i] = 1;
            long sum = last[i - 1];
            for (int j = i + 1; j < n; j++) {
                sum = (sum + last[j - 1]) % 1000000007;
                ints[j] = (sum + ints[j - 1]) % 1000000007;
            }
        }
        return (int) arr[k - 1][n - 1];
    }


}
